home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #2 / Ham Radio 2000 - Volume 2.iso / HAMV2 / TCP_IP / TNOS230S / SLHC.C < prev    next >
C/C++ Source or Header  |  1996-12-23  |  16KB  |  586 lines
  1. /*
  2.  * Routines to compress and uncompress tcp packets (for transmission
  3.  * over low speed serial lines).
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted
  9.  * provided that the above copyright notice and this paragraph are
  10.  * duplicated in all such forms and that any documentation,
  11.  * advertising materials, and other materials related to such
  12.  * distribution and use acknowledge that the software was developed
  13.  * by the University of California, Berkeley.  The name of the
  14.  * University may not be used to endorse or promote products derived
  15.  * from this software without specific prior written permission.
  16.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19.  *
  20.  *    Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21.  *    - Initial distribution.
  22.  *
  23.  *
  24.  * modified for KA9Q Internet Software Package by
  25.  * Katie Stevens (dkstevens@ucdavis.edu)
  26.  * University of California, Davis
  27.  * Computing Services
  28.  *    - 01-31-90    initial adaptation (from 1.19)
  29.  *    PPP.05    02-15-90 [ks]
  30.  *    PPP.08    05-02-90 [ks]    use PPP protocol field to signal compression
  31.  *    PPP.15    09-90     [ks]    improve mbuf handling
  32.  *    PPP.16    11-02     [karn]    substantially rewritten to use NOS facilities
  33.  *
  34.  *    - Feb 1991    Bill_Simpson@um.cc.umich.edu
  35.  *            variable number of conversation slots
  36.  *            allow zero or one slots
  37.  *            separate routines
  38.  *            status display
  39.  */
  40.  
  41. #include "global.h"
  42. #include "mbuf.h"
  43. #include "internet.h"
  44. #include "ip.h"
  45. #include "slhc.h"
  46.  
  47. static char *encode (char *cp,int16 n);
  48. static long decode (struct mbuf **bpp);
  49.  
  50.  
  51. #if !defined(_lint)
  52. static char rcsid[] OPTIONAL = "$Id: slhc.c,v 1.11 1996/12/23 20:37:36 root Exp root $";
  53. #endif
  54.  
  55. /* Initialize compression data structure
  56.  *    slots must be in range 0 to 255 (zero meaning no compression)
  57.  */
  58. struct slcompress *
  59. slhc_init( rslots, tslots )
  60. int rslots;
  61. int tslots;
  62. {
  63.     register int16 i;
  64.     register struct cstate *ts;
  65.     struct slcompress *comp;
  66.  
  67.     comp = callocw( 1, sizeof(struct slcompress) );
  68.  
  69.     if ( rslots > 0  &&  rslots < 256 ) {
  70.         comp->rstate = callocw( (unsigned)rslots, sizeof(struct cstate) );
  71.         comp->rslot_limit = uchar(rslots - 1);
  72.     }
  73.  
  74.     if ( tslots > 0  &&  tslots < 256 ) {
  75.         comp->tstate = callocw( (unsigned)tslots, sizeof(struct cstate) );
  76.         comp->tslot_limit = uchar(tslots - 1);
  77.     }
  78.  
  79.     comp->xmit_oldest = 0;
  80.     comp->xmit_current = 255;
  81.     comp->recv_current = 255;
  82.  
  83.     if ( tslots > 0 ) {
  84.         ts = comp->tstate;
  85.         for(i = comp->tslot_limit; i > 0; --i){
  86.             ts[i].this = uchar(i);
  87.             ts[i].next = &(ts[i - 1]);
  88.         }
  89.         ts[0].next = &(ts[comp->tslot_limit]);
  90.         ts[0].this = 0;
  91.     }
  92.     return comp;
  93. }
  94.  
  95.  
  96. /* Free a compression data structure */
  97. void
  98. slhc_free(comp)
  99. struct slcompress *comp;
  100. {
  101.     if ( comp == NULLSLCOMPR )
  102.         return;
  103.  
  104.     if ( comp->rstate != NULLSLSTATE )
  105.         free( comp->rstate );
  106.  
  107.     if ( comp->tstate != NULLSLSTATE )
  108.         free( comp->tstate );
  109.  
  110.     free( comp );
  111. }
  112.  
  113.  
  114. /* Encode a number */
  115. static char *
  116. encode(cp,n)
  117. register char *cp;
  118. int16 n;
  119. {
  120.     if(n >= 256 || n == 0){
  121.         *cp++ = 0;
  122.         cp = (char *) put16((unsigned char *) cp,n);
  123.     } else
  124.         *cp++ = (char) n;
  125.     return cp;
  126. }
  127.  
  128. /* Decode a number */
  129. static long
  130. decode(bpp)
  131. struct mbuf **bpp;
  132. {
  133.     register int x;
  134.  
  135.     x = PULLCHAR(bpp);
  136.     if(x == 0){
  137.         return pull16(bpp);    /* pull16 returns -1 on error */
  138.     } else {
  139.         return (long)x;        /* -1 if PULLCHAR returned error */
  140.     }
  141. }
  142.  
  143. int
  144. slhc_compress(comp, bpp, compress_cid)
  145. struct slcompress *comp;
  146. struct mbuf **bpp;
  147. int compress_cid;
  148. {
  149.     register struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);
  150.     register struct cstate *lcs = ocs;
  151.     register struct cstate *cs = lcs->next;
  152.     register int16 hlen;
  153.     register struct tcp *oth;
  154.     register unsigned long deltaS, deltaA;
  155.     register int16 changes = 0;
  156.     char new_seq[16];
  157.     register char *cp = new_seq;
  158.     struct mbuf *bp;
  159.     struct tcp th;
  160.     struct ip iph;
  161.  
  162.     /* Extract IP header */
  163.     hlen = (int16) ntohip(&iph,bpp);
  164.  
  165.     /* Bail if this packet isn't TCP, or is an IP fragment */
  166.     if(iph.protocol != TCP_PTCL || iph.offset != 0 || iph.flags.mf){
  167.         /* Send as regular IP */
  168.         if(iph.protocol != TCP_PTCL)
  169.             comp->sls_o_nontcp++;
  170.         else
  171.             comp->sls_o_tcp++;
  172.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  173.         return SL_TYPE_IP;
  174.     }
  175.     /* Extract TCP header */
  176.     hlen += (int16) ntohtcp(&th,bpp);
  177.  
  178.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  179.      *  some other control bit is set).
  180.      */
  181.     if(th.flags.syn || th.flags.fin || th.flags.rst || !th.flags.ack){
  182.         /* TCP connection stuff; send as regular IP */
  183.         comp->sls_o_tcp++;
  184.         *bpp = htontcp(&th,*bpp,NULLHEADER);
  185.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  186.         return SL_TYPE_IP;
  187.     }
  188.     /*
  189.      * Packet is compressible -- we're going to send either a
  190.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way,
  191.      * we need to locate (or create) the connection state.
  192.      *
  193.      * States are kept in a circularly linked list with
  194.      * xmit_oldest pointing to the end of the list.  The
  195.      * list is kept in lru order by moving a state to the
  196.      * head of the list whenever it is referenced.  Since
  197.      * the list is short and, empirically, the connection
  198.      * we want is almost always near the front, we locate
  199.      * states via linear search.  If we don't find a state
  200.      * for the datagram, the oldest state is (re-)used.
  201.      */
  202.     for ( ; ; ) {
  203.         if( iph.source == cs->cs_ip.source
  204.          && iph.dest == cs->cs_ip.dest
  205.          && th.source == cs->cs_tcp.source
  206.          && th.dest == cs->cs_tcp.dest)
  207.             goto found;
  208.  
  209.         /* if current equal oldest, at end of list */
  210.         if ( cs == ocs )
  211.             break;
  212.         lcs = cs;
  213.         cs = cs->next;
  214.         comp->sls_o_searches++;
  215.     };
  216.     /*
  217.      * Didn't find it -- re-use oldest cstate.  Send an
  218.      * uncompressed packet that tells the other side what
  219.      * connection number we're using for this conversation.
  220.      *
  221.      * Note that since the state list is circular, the oldest
  222.      * state points to the newest and we only need to set
  223.      * xmit_oldest to update the lru linkage.
  224.      */
  225.     comp->sls_o_misses++;
  226.     comp->xmit_oldest = lcs->this;
  227.  
  228.     goto uncompressed;
  229.  
  230. found:
  231.     /*
  232.      * Found it -- move to the front on the connection list.
  233.      */
  234.     if(lcs == ocs) {
  235.         /* found at most recently used */
  236.     } else if (cs == ocs) {
  237.         /* found at least recently used */
  238.         comp->xmit_oldest = lcs->this;
  239.     } else {
  240.         /* more than 2 elements */
  241.         lcs->next = cs->next;
  242.         cs->next = ocs->next;
  243.         ocs->next = cs;
  244.     }
  245.  
  246.     /*
  247.      * Make sure that only what we expect to change changed.
  248.      * Check the following:
  249.      * IP protocol version, header length & type of service.
  250.      * The "Don't fragment" bit.
  251.      * The time-to-live field.
  252.      * The TCP header length.
  253.      * IP options, if any.
  254.      * TCP options, if any.
  255.      * If any of these things are different between the previous &
  256.      * current datagram, we send the current datagram `uncompressed'.
  257.      */
  258.     oth = &cs->cs_tcp;
  259.  
  260.     if(iph.version != cs->cs_ip.version || iph.optlen != cs->cs_ip.optlen
  261.      || iph.tos != cs->cs_ip.tos
  262.      || iph.flags.df != cs->cs_ip.flags.df
  263.      || iph.ttl != cs->cs_ip.ttl
  264.      || th.optlen != cs->cs_tcp.optlen
  265.      || (iph.optlen > 0 && memcmp(iph.options,cs->cs_ip.options,(size_t) (int) iph.optlen) != 0)
  266.      || (th.optlen > 0 && memcmp(th.options,cs->cs_tcp.options,(size_t) (int) th.optlen) != 0)){
  267.         goto uncompressed;
  268.     }
  269.     /*
  270.      * Figure out which of the changing fields changed.  The
  271.      * receiver expects changes in the order: urgent, window,
  272.      * ack, seq (the order minimizes the number of temporaries
  273.      * needed in this section of code).
  274.      */
  275.     if(th.flags.urg){
  276.         deltaS = th.up;
  277.         cp = encode(cp,(int16)deltaS);
  278.         changes |= NEW_U;
  279.     } else if(th.up != oth->up){
  280.         /* argh! URG not set but urp changed -- a sensible
  281.          * implementation should never do this but RFC793
  282.          * doesn't prohibit the change so we have to deal
  283.          * with it. */
  284.         goto uncompressed;
  285.     }
  286.     if((deltaS = th.wnd - oth->wnd) != 0){
  287.         cp = encode(cp,(int16)deltaS);
  288.         changes |= NEW_W;
  289.     }
  290.     if((deltaA = (unsigned long) (th.ack - oth->ack)) != 0L){
  291.         if(deltaA > 0x0000ffff)
  292.             goto uncompressed;
  293.         cp = encode(cp,(int16)deltaA);
  294.         changes |= NEW_A;
  295.     }
  296.     if((deltaS = (unsigned long) (th.seq - oth->seq)) != 0L){
  297.         if(deltaS > 0x0000ffff)
  298.             goto uncompressed;
  299.         cp = encode(cp,(int16)deltaS);
  300.         changes |= NEW_S;
  301.     }
  302.  
  303.     switch(changes){
  304.     case 0:    /* Nothing changed. If this packet contains data and the
  305.          * last one didn't, this is probably a data packet following
  306.          * an ack (normal on an interactive connection) and we send
  307.          * it compressed.  Otherwise it's probably a retransmit,
  308.          * retransmitted ack or window probe.  Send it uncompressed
  309.          * in case the other side missed the compressed version.
  310.          */
  311.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  312.             break;
  313.         goto uncompressed;
  314.     case SPECIAL_I:
  315.     case SPECIAL_D:
  316.         /* actual changes match one of our special case encodings --
  317.          * send packet uncompressed.
  318.          */
  319.         goto uncompressed;
  320.     case NEW_S|NEW_A:
  321.         if(deltaS == deltaA &&
  322.             deltaS == (unsigned long)cs->cs_ip.length - hlen){
  323.             /* special case for echoed terminal traffic */
  324.             changes = SPECIAL_I;
  325.             cp = new_seq;
  326.         }
  327.         break;
  328.     case NEW_S:
  329.         if(deltaS == (unsigned long)cs->cs_ip.length - hlen){
  330.             /* special case for data xfer */
  331.             changes = SPECIAL_D;
  332.             cp = new_seq;
  333.         }
  334.         break;
  335.     default:
  336.         break;
  337.     }
  338.     deltaS = iph.id - cs->cs_ip.id;
  339.     if(deltaS != 1){
  340.         cp = encode(cp,(int16)deltaS);
  341.         changes |= NEW_I;
  342.     }
  343.     if(th.flags.psh)
  344.         changes |= TCP_PUSH_BIT;
  345.     /* Grab the cksum before we overwrite it below.  Then update our
  346.      * state with this packet's header.
  347.      */
  348.     deltaA = th.checksum;
  349.     ASSIGN(cs->cs_ip,iph);
  350.     ASSIGN(cs->cs_tcp,th);
  351.     /* We want to use the original packet as our compressed packet.
  352.      * (cp - new_seq) is the number of bytes we need for compressed
  353.      * sequence numbers.  In addition we need one byte for the change
  354.      * mask, one for the connection id and two for the tcp checksum.
  355.      * So, (cp - new_seq) + 4 bytes of header are needed.
  356.      */
  357.     deltaS = (unsigned long) (cp - new_seq);
  358.     if(compress_cid == 0 || comp->xmit_current != cs->this){
  359.         bp = *bpp = pushdown(*bpp,(int16)deltaS + 4);
  360.         cp = (char *) bp->data;
  361.         *cp++ = (char) (changes | NEW_C);
  362.         *cp++ = (char) cs->this;
  363.         comp->xmit_current = cs->this;
  364.     } else {
  365.         bp = *bpp = pushdown(*bpp,(int16)deltaS + 3);
  366.         cp = (char *) bp->data;
  367.         *cp++ = (char) changes;
  368.     }
  369.     cp = (char *) put16((unsigned char *) cp,(int16)deltaA);    /* Write TCP checksum */
  370.     memcpy(cp,new_seq,deltaS);    /* Write list of deltas */
  371.     comp->sls_o_compressed++;
  372.     return SL_TYPE_COMPRESSED_TCP;
  373.  
  374.     /* Update connection state cs & send uncompressed packet (i.e.,
  375.      * a regular ip/tcp packet but with the 'conversation id' we hope
  376.      * to use on future compressed packets in the protocol field).
  377.      */
  378. uncompressed:
  379.     iph.protocol = (char) cs->this;
  380.     ASSIGN(cs->cs_ip,iph);
  381.     ASSIGN(cs->cs_tcp,th);
  382.     comp->xmit_current = cs->this;
  383.     comp->sls_o_uncompressed++;
  384.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  385.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  386.     return SL_TYPE_UNCOMPRESSED_TCP;
  387. }
  388.  
  389.  
  390. int
  391. slhc_uncompress(comp, bpp)
  392. struct slcompress *comp;
  393. struct mbuf **bpp;
  394. {
  395.     register int changes;
  396.     long x;
  397.     register struct tcp *thp;
  398.     register struct cstate *cs;
  399.     int len;
  400.     int16 result;
  401.  
  402.     /* We've got a compressed packet; read the change byte */
  403.     comp->sls_i_compressed++;
  404.     if(len_p(*bpp) < 3){
  405.         comp->sls_i_error++;
  406.         return 0;
  407.     }
  408.     changes = PULLCHAR(bpp);    /* "Can't fail" */
  409.     if(changes & NEW_C){
  410.         /* Make sure the state index is in range, then grab the state.
  411.          * If we have a good state index, clear the 'discard' flag.
  412.          */
  413.         x = PULLCHAR(bpp);    /* Read conn index */
  414.         if(x < 0 || x > comp->rslot_limit)
  415.             goto bad;
  416.  
  417.         comp->flags &=~ SLF_TOSS;
  418.         comp->recv_current = uchar(x);
  419.     } else {
  420.         /* this packet has an implicit state index.  If we've
  421.          * had a line error since the last time we got an
  422.          * explicit state index, we have to toss the packet. */
  423.         if(comp->flags & SLF_TOSS){
  424.             comp->sls_i_tossed++;
  425.             return 0;
  426.         }
  427.     }
  428.     cs = &comp->rstate[comp->recv_current];
  429.     thp = &cs->cs_tcp;
  430.  
  431.     if ((result = pull16(bpp)) == 0xffff)    /* Read the TCP checksum */
  432.         goto bad;
  433.     x = (long) result;
  434.     thp->checksum = (int16) x;
  435.  
  436.     thp->flags.psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
  437.  
  438.     switch(changes & SPECIALS_MASK){
  439.     case SPECIAL_I:        /* Echoed terminal traffic */
  440.         {
  441.         register int16 i;
  442.         i = cs->cs_ip.length;
  443.         i -= (int16) (int) (cs->cs_ip.optlen + IPLEN + TCPLEN);
  444.         thp->ack += i;
  445.         thp->seq += i;
  446.         }
  447.         break;
  448.  
  449.     case SPECIAL_D:            /* Unidirectional data */
  450.         thp->seq += cs->cs_ip.length - (cs->cs_ip.optlen +IPLEN + TCPLEN);
  451.         break;
  452.  
  453.     default:
  454.         if(changes & NEW_U){
  455.             thp->flags.urg = 1;
  456.             if((x = decode(bpp)) == -1)
  457.                 goto bad;
  458.             thp->up = (int16) x;
  459.         } else
  460.             thp->flags.urg = 0;
  461.         if(changes & NEW_W){
  462.             if((x = decode(bpp)) == -1)
  463.                 goto bad;
  464.             thp->wnd += (int16) x;
  465.         }
  466.         if(changes & NEW_A){
  467.             if((x = decode(bpp)) == -1)
  468.                 goto bad;
  469.             thp->ack += x;
  470.         }
  471.         if(changes & NEW_S){
  472.             if((x = decode(bpp)) == -1)
  473.                 goto bad;
  474.             thp->seq += x;
  475.         }
  476.         break;
  477.     }
  478.     if(changes & NEW_I){
  479.         if((x = decode(bpp)) == -1)
  480.             goto bad;
  481.         cs->cs_ip.id += (int16) x;
  482.     } else
  483.         cs->cs_ip.id++;
  484.  
  485.     /*lint -save -e613 */
  486.     /*
  487.      * At this point, bpp points to the first byte of data in the
  488.      * packet.  Put the reconstructed TCP and IP headers back on the
  489.      * packet.  Recalculate IP checksum (but not TCP checksum).
  490.      */
  491.     len = len_p(*bpp) + IPLEN + TCPLEN + cs->cs_ip.optlen;
  492.     cs->cs_ip.length = (int16) len;
  493.  
  494.     *bpp = htontcp(thp,*bpp,NULLHEADER);
  495.     *bpp = htonip(&cs->cs_ip,*bpp,IP_CS_NEW);
  496.     /*lint -restore */
  497.     return len;
  498. bad:
  499.     comp->sls_i_error++;
  500.     return slhc_toss( comp );
  501. }
  502.  
  503.  
  504. int
  505. slhc_remember(comp, bpp)
  506. struct slcompress *comp;
  507. struct mbuf **bpp;
  508. {
  509.     register struct cstate *cs;
  510.     struct ip iph;
  511.     struct tcp th;
  512.  
  513.     /* Extract IP and TCP headers and verify conn ID */
  514.     (void) ntohip(&iph,bpp);
  515.     (void) ntohtcp(&th,bpp);
  516.     if(uchar(iph.protocol) > comp->rslot_limit) {
  517.         comp->sls_i_error++;
  518.         return slhc_toss(comp);
  519.     }
  520.  
  521.     /* Update local state */
  522.     cs = &comp->rstate[comp->recv_current = uchar(iph.protocol)];
  523.     comp->flags &=~ SLF_TOSS;
  524.     iph.protocol = TCP_PTCL;
  525.     ASSIGN(cs->cs_ip,iph);
  526.     ASSIGN(cs->cs_tcp,th);
  527.  
  528.     /* Put headers back on packet
  529.      * Neither header checksum is recalculated
  530.      */
  531.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  532.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  533.     comp->sls_i_uncompressed++;
  534.     return len_p(*bpp);
  535. }
  536.  
  537.  
  538. int
  539. slhc_toss(comp)
  540. struct slcompress *comp;
  541. {
  542.     if ( comp == NULLSLCOMPR )
  543.         return 0;
  544.  
  545.     comp->flags |= SLF_TOSS;
  546.     return 0;
  547. }
  548.  
  549.  
  550. void slhc_i_status(comp)
  551. struct slcompress *comp;
  552. {
  553.     if (comp != NULLSLCOMPR) {
  554.         tprintf("\t%10ld Cmp,"
  555.             " %10ld Uncmp,"
  556.             " %10ld Bad, "
  557.             " %10ld Tossed\n",
  558.             comp->sls_i_compressed,
  559.             comp->sls_i_uncompressed,
  560.             comp->sls_i_error,
  561.             comp->sls_i_tossed);
  562.     }
  563. }
  564.  
  565.  
  566. void slhc_o_status(comp)
  567. struct slcompress *comp;
  568. {
  569.     if (comp != NULLSLCOMPR) {
  570.         tprintf("\t%10ld Cmp,"
  571.             " %10ld Uncmp,"
  572.             " %10ld AsIs,"
  573.             " %10ld NotTCP\n",
  574.             comp->sls_o_compressed,
  575.             comp->sls_o_uncompressed,
  576.             comp->sls_o_tcp,
  577.             comp->sls_o_nontcp);
  578.         tprintf("\t%10ld Searches,"
  579.             " %10ld Misses\n",
  580.             comp->sls_o_searches,
  581.             comp->sls_o_misses);
  582.     }
  583. }
  584.  
  585.  
  586.